class BTree(object):
    
    def __init__(self,Value=None):
        if not Value is None:
            self.root = TwoThreeNode(Value)
        else:
            self.root = None
    
    def Search(self,Value):
        if self.root is None:
            return False
        else:
            return self.root.Search(Value)[0]
    
    def Insert(self,Value):
        if self.root is None:
            self.root = TwoThreeNode(Value)
        else:
            self.root.Insert(Value)
    
    def Delete(self,Value):
        pass
    
class NodeType:
    
    LEAF  = 0
    TWO   = 2
    THREE = 3
    
class TwoThreeNode(object):
    
    def __init__(self,Value):
        self._Parent = None
        self._Left   = None
        self._Middle = None
        self._Right  = None
        self.Small   = Value
        self.Large   = None
    
    def _GetParent(self):
        return self._Parent
    
    def _SetParent(self,Value):
        self._Parent = Value
    
    Parent = property(_GetParent,_SetParent)
    
    def _GetSmall(self):
        return self._Small
    
    def _SetSmall(self,Value):
        self._Small = Value
    
    Small = property(_GetSmall,_SetSmall)
    
    def _GetLarge(self):
        return self._Large
    
    def _SetLarge(self,Value):
        self._Large = Value
    
    Large = property(_GetLarge,_SetLarge)
      
    def _GetLeft(self):
        return self._Left
    
    def _SetLeft(self,Value):
        if(Value is None):
            self._Left = None
        else:
            self._Left = Value
            self._Left.Parent = self
    
    Left = property(_GetLeft,_SetLeft)
    
    def _GetMiddle(self):
        return self._Middle
    
    def _SetMiddle(self,Value):
        if(Value is None):
            self._Middle = None
        else:
            self._Middle = Value
            self._Middle.Parent = self
                
    Middle = property(_GetMiddle,_SetMiddle)
    
    def _GetRight(self):
        return self._Right
    
    def _SetRight(self,Value):
        if(Value is None):
            self._Right = None
        else:
            self._Right = Value
            self._Right.Parent = self
                
    Right = property(_GetRight,_SetRight)
    
    def IsLeaf(self):
        return (self.Left is None) and (self.Middle is None)
    
    def GetNodeType(self):
        if(self.IsLeaf()):
            return NodeType.LEAF
        elif(self.Right is None):
            return NodeType.TWO
        else:
            return NodeType.THREE
    
    NodeType = property(fget=GetNodeType)
    
    def _GetTree(self):
        Me = [[self.Small]]
        
        if(not (self.Large is None)):
            Me[0].append(self.Large)
        
        nt = self.NodeType
        
        if(nt==NodeType.LEAF):
            return Me
        
        Me.append(self.Left.Tree)
        Me.append(self.Middle.Tree)
        if(nt==NodeType.THREE):
            Me.append(self.Right.Tree)
        
        return Me
    
    Tree = property(_GetTree)
        
    
    def Insert(self, Value):
        found, node = self.Search(Value)
        
        if(found):
            return
        
        ntype = node.NodeType
        
        if(ntype==NodeType.LEAF):
            if(node.Large is None):
                if(Value<node.Small):
                    node.Large = node.Small
                    node.Small = Value
                else:
                    node.Large = Value
                return
            
            LeftBranch, Middle, RightBranch = node.Split(Value)
            
            if(node.Parent is None):
                self.Small = Middle
                self.Large = None
                self.Left = LeftBranch
                self.Middle = RightBranch
                self.Right  = None
            else:
                Parent = node.Parent
                node._ClearNode()
                Parent.Attach(LeftBranch,Middle,RightBranch)
            
            return
    
    def Split(self, Value):
        sorted = [self.Small,Value,self.Large]
        sorted.sort()
        LeftBranch  = TwoThreeNode(sorted[0])
        MediumValue = sorted[1]
        RightBranch = TwoThreeNode(sorted[2])
        
        return LeftBranch, MediumValue, RightBranch
        
    def _ClearNode(self):
        self.Parent = None
        self.Small  = None
        self.Large  = None
        self.Left   = None
        self.Middle = None
        self.Right  = None
    
    def Attach(self, LeftBranch, MediumValue, RightBranch):
        ntype = self.NodeType
        
        if(ntype==NodeType.THREE):
            NewLeft, NewMediumValue, NewRight = self.Split(MediumValue)
            
            if(MediumValue<self.Small):
                NewLeft.Left    = LeftBranch
                NewLeft.Middle  = RightBranch
                NewRight.Left   = self.Middle
                NewRight.Middle = self.Right
            elif(self.Small<MediumValue and MediumValue < self.Large):
                NewLeft.Left    = self.Left
                NewLeft.Middle  = LeftBranch
                NewRight.Left   = RightBranch
                NewRight.Middle = self.Right   
            else:
                NewLeft.Left    = self.Left
                NewLeft.Middle  = self.Middle
                NewRight.Left   = LeftBranch
                NewRight.Middle = RightBranch
            
            if(self.Parent is None):
                self.Small  = NewMediumValue
                self.Large  = None
                self.Left   = NewLeft
                self.Middle = NewRight
                self.Right  = None
            else:
                return self.Parent.Attach(NewLeft,NewMediumValue,NewRight)
                self._ClearNode()
        elif(MediumValue<self.Small):
            self.Large  = self.Small
            self.Small  = MediumValue
            self.Left   = LeftBranch
            OldMiddle  = self.Middle  #If you make a direct assignment self.Right = self.Midde,
            self.Middle = RightBranch # property logic doesn't make the correct Parent assignment.
            self.Right = OldMiddle
        else:
            self.Large  = MediumValue
            self.Middle = LeftBranch
            self.Right  = RightBranch
    
    def Search(self, Value):
        
        node = self
        while (not (node is None)):
            nt = node.NodeType

            found = node.Small==Value or node.Large==Value
            if(found or (nt==NodeType.LEAF)):
                return found, node

            if(Value<node.Small):
                node = node.Left
            elif(nt==NodeType.THREE):
                if(node.Small<Value and Value<node.Large):
                    node = node.Middle
                else:
                    node = node.Right
            else:
                node = node.Middle
        
        raise Exception("Last node type on a search should be a leaf.")
    
    def Successor(self, Value):
        
        found,node = self.Search(Value)
        
        nt = node.NodeType
        
        if found and nt==NodeType.LEAF:
            return node
        
        if nt==NodeType.TWO:
            node = node.Middle
        elif(Value>node.Large):
            node = node.Right
        else:
            node = node.Middle
        
        while (node):
            nt = node.NodeType
            if(nt==NodeType.LEAF):
                return node
            else:
                node = node.Left                        
    
    def Delete(self,Value):
        found, node = self.Search(Value)
        
        if not found: return
    
        nt = node.NodeType
        
        if nt==NodeType.LEAF:
            if(Value==node.Large):
                node.Large = None
            elif node.Large != None:
                node.Small = node.Large
                node.Large = None
            else:
                node.Small = None
                node.Parent.Redistribute(self)
                return
        else:
            succ = node.Successor(Value)
            if Value==node.Small:
                node.Small = succ.Small
                succ.Small = Value
                succ.Delete(Value)
            else:
                node.Large=succ.Small
                succ.Small = Value
                succ.Delete(Value)
            return
            
    def Merge(self,Child):
        # This method and redistribute
        # will become the template for a series of smaller
        # "borrowing" methods (Borrow left/right)
        nt = self.NodeType
        
        if nt==NodeType.TWO:
            if Child is self.Middle:
                if self.Left.NodeType==NodeType.TWO:
                    A = self.Left.Left
                    B = self.Left.Middle
                    C = self.Middle
                    self.Large = self.Small
                    self.Small = self.Left.Small
                    self.Left   = A
                    self.Middle = B
                    self.Right  = C
                    
                    if self.Parent:
                        self.Parent.Merge(self)
                
                else:
                    A = self.Left.Left
                    B = self.Left.Middle
                    C = self.Left.Right
                    D = self.Middle
                    
                    self.Middle        = TwoThreeNode(self.Small)
                    self.Small         = self.Left.Large
                    self.Left.Large    = None
                    self.Left.Right    = None
                    self.Middle.Left   = C
                    self.Middle.Middle = D
                    
            else:
                # Value < self.Small
                if self.Middle.NodeType==NodeType.TWO:
                    A = self.Left
                    B = self.Middle.Left
                    C = self.Middle.Middle
                    self.Large  = self.Middle.Small
                    self.Left   = A
                    self.Middle = B
                    self.Right  = C
                    
                    if self.Parent:
                        self.Parent.Merge(self)
                else:
                    A = self.Left
                    B = self.Middle.Left
                    C = self.Middle.Middle
                    D = self.Middle.Right
                    self.Left          = TwoThreeNode(self.Small)
                    self.Left.Left     = A
                    self.Left.Middle   = B
                    self.Small         = self.Middle.Small
                    self.Middle.Small  = self.Middle.Large
                    self.Middle.Large  = None
                    self.Middle.Left   = C
                    self.Middle.Middle = D
                    self.Middle.Right  = None
        else:
            # nt==NodeType.THREE
            if Child is self.Right: #Comes from the right branch
                if self.Middle.NodeType == NodeType.TWO:
                    self.Middle.Large = self.Large
                    self.Large        = None
                    self.Middle.Right = self.Right
                    self.Right        = None
                else:
                    D = self.Middle.Right
                    E = self.Right
                    self.Right = TwoThreeNode(self.Large)
                    self.Large = self.Middle.Large
                    self.Middle.Large = None
                    self.Right.Left = D
                    self.Right.Middle = E
                    self.Middle.Right = None
            elif Child is self.Middle:
                # Comes from the middle branch
                if self.Right.NodeType==NodeType.TWO:
                    B = self.Middle
                    C = self.Right.Left
                    D = self.Right.Middle
                    self.Middle        = TwoThreeNode(self.Large)
                    self.Large         = None
                    self.Middle.Large  = self.Right.Small
                    self.Middle.Left   = B
                    self.Middle.Middle = C
                    self.Middle.Right  = D
                    self.Right         = None
                else:
                    B = self.Middle
                    C = self.Right.Left
                    D = self.Right.Middle
                    E = self.Right.Right
                    self.Middle        = TwoThreeNode(self.Large)
                    self.Large         = self.Right.Small
                    self.Right.Small   = self.Right.Large
                    self.Right.Large   = None
                    self.Right.Right   = None
                    self.Middle.Left   = B
                    self.Middle.Middle = C
                    self.Right.Left    = D
                    self.Right.Middle  = E
            else:
                # Child is self.Left
                if self.Middle.NodeType==NodeType.TWO:
                    A = self.Left
                    B = self.Middle.Left
                    C = self.Middle.Middle
                    D = self.Right
                    self.Left        = TwoThreeNode(self.Small)
                    self.Left.Large  = self.Middle.Small
                    self.Small       = self.Large
                    self.Large       = None
                    self.Right       = None
                    self.Left.Left   = A
                    self.Left.Middle = B
                    self.Left.Right  = C
                    self.Middle      = D
                else:
                    A = self.Left
                    B = self.Middle.Left
                    C = self.Middle.Middle
                    D = self.Middle.Right
                    self.Left          = TwoThreeNode(self.Small)
                    self.Left.Left     = A
                    self.Left.Middle   = B
                    self.Small         = self.Middle.Small
                    self.Middle.Small  = self.Middle.Large
                    self.Middle.Large  = None
                    self.Middle.Left   = C
                    self.Middle.Middle = D
                    self.Middle.Right  = None
                
    
    def Redistribute(self,Child):
        nt = self.NodeType
        
        assert(nt!=NodeType.LEAF) # this function should only be called by a leaf
        
        if nt==NodeType.TWO: #TWO Node
            if(Child is self.Middle): # Redistribute call made from the middle path
                if(not self.Left.Large is None):
                    self.Middle.Small=self.Small
                    self.Small = self.Left.Large
                    self.Left.Large = None
                else: # Redistribute call made from the left path
                    self.Large = self.Small
                    self.Small = self.Left.Small
                    self.Left = None
                    self.Middle = None
                    if(not self.Parent is None):
                        self.Parent.Merge(self)
                    return
            else:
                if(not self.Middle.Large is None):
                    self.Left.Small = self.Small
                    self.Small = self.Middle.Small
                    self.Middle.Small = self.Middle.Large
                    self.Middle.Large = None
                else:
                    self.Large = self.Middle.Small
                    self.Left = None
                    self.Middle = None
                    if(not self.Parent is None):
                        self.Parent.Merge(self)
        else: # THREE Node
            if(Child is self.Left): # Redistribute call made from left path
                if self.Middle.Large is None:
                    self.Left.Small = self.Small
                    self.Left.Large = self.Middle.Small
                    self.Small = self.Large
                    self.Large = None
                    self.Middle = self.Right
                    self.Right = None
                else:
                    self.Left.Small = self.Small
                    self.Small = self.Middle.Small
                    self.Middle.Small = self.Middle.Large
                    self.Middle.Large = None
            elif(Child is self.Middle): # Redistribute call made from middle branch
                if self.Right.Large is None:
                    self.Middle.Small = self.Large
                    self.Large = None
                    self.Middle.Large = self.Right.Small
                    self.Right = None
                else:
                    self.Middle.Small = self.Large
                    self.Large = self.Right.Small
                    self.Right.Small = self.Right.Large
                    self.Right.Large = None
            else: # Redistribute call made from right branch
                if not self.Middle.Large is None:
                    self.Right.Small = self.Large
                    self.Large = self.Middle.Large
                    self.Middle.Large = None
                else:
                    self.Middle.Large = self.Large
                    self.Large = None
                    self.Right = None
                
            
    
if(__name__=="__main__"):
    Inserts = [1,2,-1,-2,3,4,7,5,6,-3]
    Node = TwoThreeNode(0)
    print Node.Tree
    for iCounter in Inserts:
        Node.Insert(iCounter)
        print "Insert %s: %s " % (iCounter, Node.Tree)
        
        
